public class demo7 {

        public static void main(String[] args) {
            int maxLength = 24;
            long[][] dp = new long[maxLength + 1][16];
            int[] countOnes = new int[16];

            // 预处理每个四位状态的1的个数
            for (int s = 0; s < 16; s++) {
                countOnes[s] = Integer.bitCount(s);
            }

            // 初始化长度为4的情况
            for (int s = 0; s < 16; s++) {
                dp[4][s] = 1;
            }

            // 动态规划填充
            for (int i = 5; i <= maxLength; i++) {
                for (int prev = 0; prev < 16; prev++) {
                    for (int c = 0; c < 2; c++) {
                        // 计算左移后四位中的1的个数
                        int highestBit = (prev & 0b1000) >> 3;
                        int onesAfterShift = countOnes[prev] - highestBit;
                        int total = onesAfterShift + c;

                        if (total > 3) continue;  // 超过3个1则跳过
                        int newState = ((prev << 1) & 0b1111) | c;
                        dp[i][newState] += dp[i - 1][prev];
                    }
                }
            }

            // 计算结果
            long result = 0;
            for (int s = 0; s < 16; s++) {
                result += dp[maxLength][s];
            }
            System.out.println(result);  // 输出：1048232
        }
    }


